package hh.leecode;

import java.util.*;

/**
 * 4. 寻找两个正序数组的中位数
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
 * <p>
 * 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * 示例 2：
 * <p>
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 * 示例 3：
 * <p>
 * 输入：nums1 = [0,0], nums2 = [0,0]
 * 输出：0.00000
 * 示例 4：
 * <p>
 * 输入：nums1 = [], nums2 = [1]
 * 输出：1.00000
 * 示例 5：
 * <p>
 * 输入：nums1 = [2], nums2 = []
 * 输出：2.00000
 */
public class a4寻找两个正序数组的中位数 {


    public static void main(String[] args) {
        new a4寻找两个正序数组的中位数().a(new int[]{}, new int[]{1, 2, 3, 4, 5});
        new a4寻找两个正序数组的中位数().a(new int[]{1}, new int[]{2, 3, 4, 5});
        new a4寻找两个正序数组的中位数().a(new int[]{1, 3, 5, 7, 9}, new int[]{2});
        new a4寻找两个正序数组的中位数().a(new int[]{}, new int[]{1});
        new a4寻找两个正序数组的中位数().a(new int[]{2}, new int[]{});
        new a4寻找两个正序数组的中位数().a(new int[]{1, 3}, new int[]{2});
        new a4寻找两个正序数组的中位数().a(new int[]{1, 2}, new int[]{3, 4});
        new a4寻找两个正序数组的中位数().a(new int[]{0, 0}, new int[]{0, 0});
    }

    public double a(int[] nums1, int[] nums2) {
        double d = findMedianSortedArrays(nums1, nums2);
        System.out.println(d);
        return d;
    }


    int nextInsertIdx = 0;
    int queueCount = 0;
    int[] queue = new int[2];
    boolean hasTwo = false;


    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int len1 = nums1.length;
        int len2 = nums2.length;
        this.hasTwo = (len1 + len2) % 2 == 0;
        //如果有两个中位数，这个mid指的是中位数在第几个元素
        // 125 mid=1+1  1234 mid=2+1
        int mid = (len1 + len2) / 2 + 1;

        int finishEnqueue = 0;
        for (int i = 0, j = 0; ; ) {
            if (queueCount == mid) {
                break;
            }

            if (i < len1) {
                if (j < len2) {
                    // 两个都有数据
                    if (nums1[i] < nums2[j]) {
                        enqueue(nums1[i]);
                        i++; //小的元素需要++，找他大哥来比较
                    } else {
                        enqueue(nums2[j]);
                        j++; //小的元素需要++，找他大哥来比较
                    }
                } else {
                    // 如果nums2没有大哥了
                    if (finishEnqueue++ > 0) {// 避免 【1 3】 【2 4】这样的情况，两个数组各取一个
                        int midIdx = mid - nums2.length - 1;
                        return hasTwo ? (nums1[midIdx - 1] + nums1[midIdx]) / 2.0 : nums1[midIdx];
                    }
                    enqueue(nums1[i++]);
                }
            } else {
                // 如果nums1没有大哥了  else不需要考虑另一个数组也没有元素，因为找中位数，如果两个都没元素，早就找到了
                // todo 这里可以优化，如果这个一个数组一百万，一个数组只有元素1，这里不需要遍历了，直接计算即可
                if (finishEnqueue++ > 0) {
                    int midIdx = mid - nums1.length - 1;
                    return hasTwo ? (nums2[midIdx - 1] + nums2[midIdx]) / 2.0 : nums2[midIdx];
                }
                enqueue(nums2[j++]);

            }
        }

        int middle = queue[(nextInsertIdx + 1) % 2];
        if (hasTwo) {
            return (middle + queue[nextInsertIdx]) / 2.0;
        } else {
            return middle;
        }
    }

    // 假装入队列，队列只保留两个元素
    private void enqueue(int i) {
        queue[nextInsertIdx++] = i;
        nextInsertIdx %= 2;
        queueCount++;
    }
}






